package 每日一题;

import publicClass.TreeNode;

import java.util.ArrayList;

/**
 * 给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。
 *
 * 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
 * 反转后，返回树的根节点。
 *
 * 完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
 *
 * 节点的 层数 等于该节点到根节点之间的边数。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [2,3,5,8,13,21,34]
 * 输出：[2,5,3,8,13,21,34]
 * 解释：
 * 这棵树只有一个奇数层。
 * 在第 1 层的节点分别是 3、5 ，反转后为 5、3 。
 * 示例 2：
 *
 *
 * 输入：root = [7,13,11]
 * 输出：[7,11,13]
 * 解释：
 * 在第 1 层的节点分别是 13、11 ，反转后为 11、13 。
 * 示例 3：
 *
 * 输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
 * 输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
 * 解释：奇数层由非零值组成。
 * 在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
 * 在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。
 *
 *
 * 提示：
 *
 * 树中的节点数目在范围 [1, 214] 内
 * 0 <= Node.val <= 105
 * root 是一棵 完美 二叉树
 */
public class T2415_反转二叉树的奇数层 {

    //使用层序遍历 反转奇数层
    public TreeNode reverseOddLevels(TreeNode root) {

        //当前层的节点
        ArrayList<TreeNode> curr = new ArrayList<>();
        //下一层的节点
        ArrayList<TreeNode> next;
        //层数
        int level = 0;

        curr.add(root);

        //当前层的节点不为空
        while (!curr.isEmpty()) {

            //当前行号 是奇数 先反转再取下一层的节点
            if (level % 2 == 1) {
                int left = 0;
                int right = curr.size() - 1;
                //使用双指针反转节点的值
                while (left < right) {
                    int temp = curr.get(left).val;
                    curr.get(left).val = curr.get(right).val;
                    curr.get(right).val = temp;
                    left++;
                    right--;
                }
            }
            //取下一层的节点
            next = new ArrayList<>();
            for (TreeNode node : curr) {

                if (node.left != null) {
                    next.add(node.left);
                }
                if (node.right != null) {
                    next.add(node.right);
                }
            }
            //将下一层赋值给当前层 遍历下一层节点
            curr = next;
            //层数加1
            level++;

        }
        return root;
    }
}
